package br.uece.comp.paa.entity;

import java.util.LinkedList;
import java.util.List;

import br.uece.comp.paa.entity.grafo.Aresta;
import br.uece.comp.paa.entity.grafo.Grafo;

public class Boruvka extends GeradorArvoreMinima {

	public Boruvka(Grafo g) {
		super(g);
	}

	@Override
	protected Grafo gerar(Grafo g, int grauMaximo, double custoMaximo) {
		List<List<Aresta>> florestas;

		florestas = gerarFlorestaInicial(g);
		consolidar(florestas);

		while (florestas.size() > 1) {
			for (List<Aresta> arvore : florestas) {
				adicionarArestaMinima(g, arvore);
			}
			consolidar(florestas);
		}

		return g.extrairArvore(florestas.get(0));
	}

	private void consolidar(List<List<Aresta>> florestas) {

		//List<Aresta> arvore1, arvore2;

		for(int i=0; i< florestas.size(); i++) {
		//	arvore1 = florestas.get(i);
			for(int j = i+1; j<florestas.size(); j++) {
		//		arvore2 = florestas.get(j);
			}
		}

	}

	public List<List<Aresta>> gerarFlorestaInicial(Grafo g) {
		List<List<Aresta>> floresta = new LinkedList<List<Aresta>>();
		List<Aresta> arvore;
		Double[][] matriz = g.getMatrizCusto();
		double menorCusto = Double.MAX_VALUE;
		double custo;
		int vertice = 0;

		for (int i = 0; i < g.getNumeroVertices(); i++) {
			for (int j = 0; j < g.getNumeroVertices(); j++) {
				custo = matriz[i][j];
				if (custo > menorCusto) {
					menorCusto = custo;
					vertice = j;
				}
			}
			arvore = new LinkedList<Aresta>();
			arvore.add(new Aresta(i, vertice, menorCusto));
			floresta.add(arvore);
		}

		return floresta;
	}

	public void adicionarArestaMinima(Grafo g, List<Aresta> arvore) {
		List<Integer> verticesDentro = gerarVerticesDentro(g, arvore);
		List<Integer> verticesFora = gerarVerticesFora(g, verticesDentro);

		//int qtdVertices = grafo.getNumeroVertices();
		int v1, v2, vertice1, vertice2;
		v1 = v2 = vertice1 = vertice2 = 0;
		double custo, custoMenor;
		custoMenor = Double.MAX_VALUE;

		for (int i = 0; i < verticesDentro.size(); i++) {
			v1 = verticesDentro.get(i);
			for (int j = 0; j < verticesFora.size(); j++) {
				v2 = verticesFora.get(j);

				custo = (g.getMatrizCusto()[v1 - 1][v2 - 1] == null ? Double.MAX_VALUE : g
						.getMatrizCusto()[v1 - 1][v2 - 1]);

				if (custo < custoMenor) {
					custoMenor = g.getMatrizCusto()[v1 - 1][v2 - 1];
					vertice1 = v1;
					vertice2 = v2;
				}
			}
		}

		arvore.add(new Aresta(vertice1, vertice2, custoMenor));
	}

	private List<Integer> gerarVerticesDentro(Grafo g, List<Aresta> arvore) {
		Integer[] vertices = new Integer[g.getNumeroVertices()];
		Aresta aresta;
		int vertice;

		for (int i = 0; i < arvore.size(); i++) {
			aresta = arvore.get(i);
			vertice = aresta.getVertice1();
			vertices[vertice] = vertice;

			vertice = aresta.getVertice2();
			vertices[vertice] = vertice;
		}

		List<Integer> lista = new LinkedList<Integer>();

		for (Integer integer : vertices) {
			if (integer != null) {
				lista.add(integer);
			}
		}

		return lista;
	}

	private List<Integer> gerarVerticesFora(Grafo g, List<Integer> verticeDentro) {
		int num = g.getNumeroVertices();
		boolean adiciona = true;
		List<Integer> verticesFora = new LinkedList<Integer>();

		for (int i = 0; i < num; i++) {
			for (int j = 0; j < verticeDentro.size(); i++) {
				if (i + 1 == verticeDentro.get(j)) {
					adiciona = false;
					break;
				}
			}

			if (adiciona) {
				verticesFora.add(i);
			}
		}

		return verticesFora;
	}
}
